/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package Algorithmes;

import Modele.*;
import java.util.ArrayList;

/**
 *
 * @author Administrator
 */
public class Heuristiques {

    private Solution solution;
    private int origine;

    public Solution getSolution() {
        return solution;
    }

    public Heuristiques(TSPLib_Data graphe, int origine) {

        this.origine = origine;
        solution = new Solution();
        int laMatrice[][] = new int[graphe.getNbrSommets()][graphe.getNbrSommets()];


        int i,j;
        for (i=0;i<graphe.getNbrSommets();i++){
            for (j=0;j<graphe.getNbrSommets();j++)
                laMatrice[i][j] = 0;
        }                

        solution.setSolMatrice(laMatrice);

        solution.getSolMatrice()[origine][origine] = 1;
        int sommeAssignement = 0;
        for (i=0;i<graphe.getNbrSommets();i++){
            if (i!=origine){
                solution.getSolMatrice()[i][origine] = 2;
                solution.getSolMatrice()[origine][i] = -2;
                sommeAssignement = sommeAssignement + graphe.getCoutAssignement(i, origine);
            }
        }
        
        solution.setCoutTotalCycle(0);
        solution.setCoutTotalAssignement(sommeAssignement);

        }


   // Heuristique de base : chercher une solution acceptable

    public void heuristiqueDeBase(TSPLib_Data graphe){
        
        Cycle cycle = new Cycle(graphe);
        Solution solTmp;


        boolean arret = false;
        double nouveauL = -100;
        boolean ajoutable = true; //boolean qui signifie qu'il y a encore des points à ajouter dans le cycle)
        ArrayList <Integer> listeAIgnorer = new ArrayList <Integer> ();

        while (ajoutable == true && nouveauL < 0 ){
        //Boucle pricipale, on s'arrete quand il n'y a plus de point à ajouter ou si les points restants sont mauvais



            // Chercher le sommet le plus proche du cycle
            float distanceMin = Float.MAX_VALUE;
            int sommetProche = -1;
            int sommetCycle = -1;

            for (int i=0 ; i < graphe.getNbrSommets(); i++){

                // Si le pount i est dans le cycle
                if (solution.getSolMatrice()[i][i] == 1){
                    for (int j=0;j<graphe.getNbrSommets();j++){

                        // Si le point j n'est pas dans le cycle et la distance est meilleur et le point n'est pas dans liste à ignorer
                        if (solution.getSolMatrice()[j][j] != 1 && graphe.getDistance(i, j) < distanceMin && !listeAIgnorer.contains(j)){
                            distanceMin = graphe.getDistance(i, j);
                            sommetProche = j;
                            sommetCycle = i;
                        }
                    }
                }

            }
            
            if (sommetProche == -1){
                ajoutable = false;
            }
            else {
            
            solTmp = solution.cloner();

            // Ajouter ce sommet dans le cycle en calculant l'incrémentation de cout de cycle (methode Inc)
            int inc = cycle.Inc(sommetProche, solTmp);

            // Calculer la décrémentation de cout d'assignement (méthode Dec)
            int dec = cycle.Dec(sommetProche, solTmp);

            // Calculer nouveauL avec Inc, Dec selon les 5 valeurs possibles de Lamda
            nouveauL = cycle.L_i_Lamda(0.3, inc, dec);

            // Si la nouvelle solution est meilleur, solution = soltmp
            if (nouveauL < 0){
                solution = solTmp;
                solution.setCoutTotalCycle(solution.getCoutTotalCycle()+inc);
                solution.setCoutTotalAssignement(solution.getCoutTotalAssignement()-dec);
                listeAIgnorer.clear();
            }else{
                listeAIgnorer.add(sommetProche);
                //System.out.println(sommetProche);
            }
            
        //Fin de boucle
            }
        }
    }
}
